package 动态规划;

/**
 * 状态F(i,j)：从前i个商品中选择，包的大小为j时的最大价值。
 * 转移方程：
 *    第i个商品可以放入大小为j的包中：
 *        F(i,j) = Math.max(F(i-1,j) + V(i-1), F(i-1,j-A[i-1]) + V(i-1))
 *             // F(i-1,j): 表示不把第i个物品放入背包中， 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
 *             // F(i-1, j - A[i]) + V[i]：表示把第i个物品放入背包中，价值增加V[i],但是需要腾出A[i-1]的大小放第i个商品
 *             // 这里由于下标会
 *        F(i,j) = F(i-1,j)
 * 初始状态：
 *         F(i,0) = 0  包空间为0，放不下，价值为0
 *         F(0,j) = 0  没有物品，没有价值
 * 返回值：F(n,m)
 */
public class LintCode125_背包问题 {

    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        int n = A.length;
        int[][] maxValue = new int[n+1][m+1];

        for (int i = 1; i <= n; i++) {
            // 这里需要注意，我们的一维数组需要从后向前更新
            // 因为在计算后面的时候，需要用到前面的数据，也就是上一行的数据
            for (int j = 1; j <= m; j++) {
                if(A[i-1] <= j) {
                    maxValue[i][j] = Math.max(maxValue[i-1][j],
                            maxValue[i-1][j-A[i-1]] + V[i-1]);
                }else {
                    maxValue[i][j] = maxValue[i-1][j];
                }
            }
        }
        return maxValue[n][m];
    }
    /*优化算法：
    上面的算法在计算第i行元素时，只用到第i-1行的元素，所以二维的空间可以优化为一维空间
    但是如果是一维向量，需要从后向前计算，
    因为后面的元素更新需要依靠前面的元素未更新（模拟二维矩阵的上一行的值） 的值
    */
    public int backPackII2(int m, int[] A, int[] V) {
        int n = A.length;
        int[] maxValue = new int[m+1];

        for (int i = 1; i <= n; i++) {
            for (int j = m; j > 0; j--) {
                if(A[i-1] <= j) {
                    maxValue[j] = Math.max(maxValue[j],
                            maxValue[j-A[i-1]] + V[i-1]);
                }
            }
        }
        return maxValue[m];
    }
}
